/*
 * @Author: Vorga
 * @LastEditors: Vorga
 */
#include <string.h>
#include <math.h>

#include "tree.h"

TreeArray* create_ta(char* level)
{
    TreeArray* tree = malloc(sizeof(TreeArray));
    tree->cnt = strlen(level);
    tree->size = strlen(level);
    tree->arr = malloc(tree->size);
    strcpy(tree->arr, level);
    return tree;
}

size_t _height_ta(TreeArray* tree, size_t index)
{
    if ('#' == tree->arr[index] || index >= tree->size) return 0;
    size_t lh = _height_ta(tree, index * 2 + 1);
    size_t rh = _height_ta(tree, index * 2 + 2);
    return lh > rh ? lh + 1 : rh + 1;
}

size_t height_ta(TreeArray* tree)
{
    return _height_ta(tree, 0);
}

bool _is_balance_ta(TreeArray* tree, size_t index)
{
    if ('#' == tree->arr[index] || index >= tree->size) return true;
    size_t l = _height_ta(tree, index * 2 + 1);
    size_t r = _height_ta(tree, index * 2 + 2);
    size_t tmp = l > r ? l - r : r - l;
    return 1 >= tmp && _is_balance_ta(tree, l) && _is_balance_ta(tree, r);
}

bool is_balance_ta(TreeArray* tree)
{
    return _is_balance_ta(tree, 0);
}

size_t density_ta(TreeArray* tree)
{
    size_t cnt = 0;
    for (size_t i = 0; i < tree->size; i++) {
        if ('#' != tree->arr[i])cnt++;
    }
    return cnt;
}

void _dlr_ta(TreeArray* tree, size_t index)
{
    if ('#' == tree->arr[index] || index >= tree->size)return;
    printf("%c ", tree->arr[index]);
    _dlr_ta(tree, index * 2 + 1);
    _dlr_ta(tree, index * 2 + 2);
}

void dlr_ta(TreeArray* tree)
{
    _dlr_ta(tree, 0);
}

void lv_ta(TreeArray* tree)
{
    for (size_t i = 0; i < tree->size; i++) {
        if ('#' != tree->arr[i]) printf("%c ", tree->arr[i]);
    }
}
